package com.wyp168.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName FindClosestElementsSolution
 * @Description TODO 从一个已排序的数组中找到最接近x的K个元素，并返回集合
 * @Author wyp168
 * @Date 2022/8/25 06:10
 */
public class FindClosestElementsSolution {
    public static void main(String[] args) {

        FindClosestElementsSolution findClosestElementsSolution = new FindClosestElementsSolution();
        int[] arr = {1,2,4,5};
        int x = 3;
        int k = 3;
        System.out.println(findClosestElementsSolution.findClosestElements(arr, k, x));
    }


    //从一个已排序的数组中找到最接近x的K个元素，并返回集合
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        //封装返回结果
        List<Integer> ans = new ArrayList<>();
        int length = arr.length;
        //如果所需要长度大于数组的总长度，那么直接返回数组即可
        if (length <= k) {
            for (int i = 0; i < length; i++) {
                ans.add(arr[i]);
            }
            return ans;
        }
        //基本思路：先进行边界值判断，如果x小于arr[0]，那么，我们直接去除右边界的值即可
        if (x <= arr[0]) {
            int i = 0;
            while (i < k && i < length) {
                ans.add(arr[i]);
                i ++;
            }
            return ans;
        }
        //如果x大于arr[arr.length - 1]，那么，我们直接去除做】左边界的值即可
        if (arr[arr.length - 1] <= x) {
            for (int i = length - k; i < length; i++) {
                ans.add(arr[i]);
            }
            return ans;
        }

        //如果x的值位于数组中间，我们通过比较左右边界值（arr[left] 及 arr[right]）来确定区域，并且封装到集合中返回
        int left = 0;
        int right = length - 1;
        int loopCount = length - k;
        while (loopCount > 0) {
            if ( Math.abs(x - arr[left]) > Math.abs(arr[right] - x) ) {
                left ++;
            } else {
                right --;
            }
            loopCount --;
        }
        for (int i = left; i <= right; i++) {
            ans.add(arr[i]);
        }
        return ans;
    }
}
